The problem can be found at the following link: Question Link
Simple direct approach, I iterate through the array, calculate the sum of its elements, and check if the sum is a prime number. If it's not, I increment the sum until it becomes prime. The count of increments is the minimum number of operations needed to transform the array into a prime array.
- Time Complexity:
O(N * sqrt(S))
, whereN
is the size of the array, andS
is the sum of array elements. - Auxiliary Space Complexity:
O(1)
, as no extra space is used.
class Solution {
public:
bool isprime(int& n) {
if (n == 1)
return false;
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
int minNumber(int arr[], int N) {
int sum = 0;
for (int i = 0; i < N; i++)
sum += arr[i];
int cnt = 0;
while (!isprime(sum)) {
++cnt;
++sum;
}
return cnt;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.